package com.arron.algorithm.sort;


import java.util.Arrays;

/**
 * 归并排序
 *
 */
public class MergeSort {


    public static void main(String[] args) {

        int[] a = {1,5,2,2,0,5};

        int[] res = sort(a);

        print(res);

//        int[] reslut= new int[3];
//        System.out.println(reslut.length);

    }

    public static void print(int[] array){
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }

    //todo 明天参考书上实现
    public static int[]  sort(int[] array){

        if(array.length < 2){
            return array;
        }
        //1,2,3,4,5

        //mid == 5/2=2

        int mid = array.length/2;

        int[] left = Arrays.copyOfRange(array, 0, mid);
        //left = [1,2]

        int[] right = Arrays.copyOfRange(array, mid, array.length);
        //right = [3,4,5]

        return merge(sort(left),sort(right));

    }

    /**
     * 合并两个数组成有序数组 ,前提是两个数组已有序
     * @param left
     * @param right
     * @return
     */
    private static int[] merge(int[] left, int[] right) {

        int[] reslut= new int[left.length+right.length];

        for (int i = 0,j=0,index = 0; index < reslut.length; index++) {

            if (i>= left.length){
                //如果左边的数组比较完了，就直接取右边的数组
                reslut[index] = right[j++];
            }else if(j>= right.length){
                reslut[index] = left[i++];
            }else if (left[i] > right[j]){
                reslut[index] = right[j++];
            }else {
                reslut[index] = left[i++];
            }

        }

        return reslut;
    }


}
